package LeetCode_力扣;
//剑指 Offer 22. 链表中倒数第k个节点

/**
 * 思路一：统计总长度。如果我们知道了链表的总长度 n ，那么
 * 所谓的倒数第 k 个数， 就是从 head 走 n - k 步的节点
 */
//这里还需要考虑k的合法性

/*

public class getKthFromEnd_剑指offer_22 {
    public ListNode getKthFromEnd(ListNode head, int k) {
        int conut = 0;
        for (ListNode x = head; x != null ; x = x.next) {
                conut ++;
        }
        int midd = conut - k;
        if(midd < 0 ){
            return head;
        }
        for (int i = 0; i < midd ; i++) {
            head = head.next;
        }
        return head;
    }
}

*/

/**
 * 思路二：相对距离法。 引入两个引用，slow和 fast。
 * 先让 fast 走 k 步，然后两个引用再同时开始依次向后移动
 * 因为他们相距的距离是不变的，当 fast走到 null头的时候，
 * 此时的 slow正好落在 倒数第 k 个节点的位置上。
 * 不懂的可以逆着想，如果我们让一个指针落在 k 上，一个指针落在 null末尾
 * 它们同时向 左走，当那个落在 k上的指针到头节点的时候停止。一个道理。
 */
//注释：任需要考虑边界问题，k的合法性。

/*

public class getKthFromEnd_剑指offer_22 {
    public ListNode getKthFromEnd(ListNode head, int k) {

        //边界
        if(head == null || k < 0){
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;

        for (int i = 0; i < k; i++) {

            if(fast == null){
                //k的合理性 如果还没移动完就走到头了，k肯定是超标了
                return head;
            }
            fast = fast.next;
        }
        while(fast != null){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

 */








/*

public class getKthFromEnd_剑指offer_22 {
    public ListNode getKthFromEnd(ListNode head, int k) {

    }
}

 */


//class ListNode {
//    int val;
//    ListNode next;
//
//    ListNode(int x) {
//        val = x;
//    }
//}
